#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;

const int MAXN = 3.5e4+10;
const int inf = 1e9;

inline int abs(int x){return x < 0 ? -x : x;}

int a[MAXN],b[MAXN],d[MAXN],dp[MAXN],n,e;
ll f[MAXN],sl[MAXN],sr[MAXN];

vector<int> l[MAXN];

int main (){
	scanf("%d",&n); for(int i = 1;i <= n;i++) scanf("%d",&a[i]),b[i] = a[i]-i;b[0] = -inf;b[n+1] = inf;
	d[++e] = b[1];dp[1] = 1;l[dp[1]].pb(1);
	for(int i = 2;i <= n+1;i++){
		if(b[i] >= d[e]) d[++e] = b[i],dp[i] = e,l[dp[i]].pb(i);
		else{
			int p = upper_bound(d+1,d+e+1,b[i])-d; d[p] = b[i];
			dp[i] = p,l[dp[i]].pb(i);
		}
	}
	printf("%d\n",n-e+1);
	l[0].pb(0);memset(f,0x3f,sizeof(f));f[0] = 0;
	for(int i = 1;i <= n+1;i++){
		for(int j = 0,x;j < l[dp[i]-1].size();j++){
			x = l[dp[i]-1][j]; if(x > i || b[x] > b[i]) continue;
			sl[x] = 0;for(int k = x+1;k <= i;k++) sl[k] = sl[k-1] + abs(b[k]-b[x]);
			sr[i] = 0;for(int k = i-1;k >= x;k--) sr[k] = sr[k+1] + abs(b[k]-b[i]);
			for(int k = x;k < i;k++) f[i] = min(f[i],sl[k] + sr[k+1] + f[x]);
		}
	}
	printf("%lld\n",f[n+1]);return 0;		
}
